package org.ala.everyday;

import java.util.*;

/**
 * 给你一个字符串数组 ideas 表示在公司命名过程中使用的名字列表。公司命名流程如下：
 *
 * 从 ideas 中选择 2 个 不同 名字，称为 ideaA 和 ideaB 。
 * 交换 ideaA 和 ideaB 的首字母。
 * 如果得到的两个新名字 都 不在 ideas 中，那么 ideaA ideaB（串联 ideaA 和 ideaB ，中间用一个空格分隔）是一个有效的公司名字。
 * 否则，不是一个有效的名字。
 * 返回 不同 且有效的公司名字的数目。
 *
 *
 *
 * 示例 1：
 *
 * 输入：ideas = ["coffee","donuts","time","toffee"]
 * 输出：6
 * 解释：下面列出一些有效的选择方案：
 * - ("coffee", "donuts")：对应的公司名字是 "doffee conuts" 。
 * - ("donuts", "coffee")：对应的公司名字是 "conuts doffee" 。
 * - ("donuts", "time")：对应的公司名字是 "tonuts dime" 。
 * - ("donuts", "toffee")：对应的公司名字是 "tonuts doffee" 。
 * - ("time", "donuts")：对应的公司名字是 "dime tonuts" 。
 * - ("toffee", "donuts")：对应的公司名字是 "doffee tonuts" 。
 * 因此，总共有 6 个不同的公司名字。
 *
 * 下面列出一些无效的选择方案：
 * - ("coffee", "time")：在原数组中存在交换后形成的名字 "toffee" 。
 * - ("time", "toffee")：在原数组中存在交换后形成的两个名字。
 * - ("coffee", "toffee")：在原数组中存在交换后形成的两个名字。
 * 示例 2：
 *
 * 输入：ideas = ["lack","back"]
 * 输出：0
 * 解释：不存在有效的选择方案。因此，返回 0 。
 *
 *
 * 提示：
 *
 * 2 <= ideas.length <= 5 * 104
 * 1 <= ideas[i].length <= 10
 * ideas[i] 由小写英文字母组成
 * ideas 中的所有字符串 互不相同
 *
 * @author ala
 * @date 2024-09-25 01:02
 */
public class Q2306 {

    public static void main(String[] args) {
        Q2306 q = new Q2306();

//        String[] ideas = {"coffee","donuts","time","toffee"};
//        String[] ideas = {"lack","back"};
//        String[] ideas = {"aaa","baa","caa","bbb","cbb","dbb"};
        String[] ideas = {"phhrrjjcm","zjfkpps","pm","fnpduelfe","mxtvjnq"};

        System.out.println(q.distinctNames(ideas));
    }

    public long distinctNames(String[] ideas) {
//        return V1(ideas);
        return V2(ideas);
    }
    /**
     *  1）按前缀分组，则组内的串无法互相替换
     *  2）组间的单词，只要后缀不相同就可以互相组合
     *  3）两两组合，求出存在公共后缀的部分，组合数 = (G1 - 交集数量) * (G2 - 交集数量)
     */
    protected long V1(String[] ideas) {
        //  按首字母分组
        Set<Integer>[] groups = new Set[26];
        Arrays.setAll(groups, k -> new HashSet<>());
        Tire tire = new Tire();
        for (String idea : ideas) {
            groups[idea.charAt(0) - 'a'].add(tire.append(idea.substring(1)));
        }

        //  每个分组两两组合，计算交集
        long res = 0;
        for (int i = 1 ; i < 26 ; i++) {
            for (int j = 0 ; j < i ; j++) {
                long m = 0;
                for (int id : groups[i]) {
                    if (groups[j].contains(id)) {
                        m++;
                    }
                }
                res += (groups[i].size() - m) * (groups[j].size() - m);
            }
        }
        return res << 1;
    }
    static int SID = 0;
    /**
     *  字典树int化
     */
    static class Tire {
        Tire[] children = new Tire[26];
        boolean lear;
        int id;
        public int append(String str) {
            Tire crt = this;
            char[] cs = str.toCharArray();
            for (char c : cs) {
                int i = c - 'a';
                if (crt.children[i] == null) {
                    crt.children[i] = new Tire();
                }
                crt = crt.children[i];
            }
            if (crt.lear) {return crt.id;}
            else {
                crt.lear = true;
                return crt.id = ++SID;
            }
        }
    }


    /**
     *  1）遍历的同时维护集合大小和交集大小
     */
    protected long V2(String[] ideas) {
        //  每个集合大小，每个交集大小
        long[] size = new long[26];
        long[][] intersection = new long[26][26];
        //  后缀在哪些集合出现过
        Map<String, Integer> marks = new HashMap<>();
        for (String idea : ideas) {
            int b = idea.charAt(0) - 'a';
            size[b]++;
            String suffix = idea.substring(1);
            int mark = marks.getOrDefault(suffix, 0);
            marks.put(suffix, mark | (1 << b));
            //  累加suffix出现过的集合的交集数量
            for (int i = 0 ; i < 26 ; i++) {
                if ((mark >> i & 1) > 0) {
                    intersection[i][b]++;
                    intersection[b][i]++;
                }
            }
        }

        //  计算所有集合两两相交
        long res = 0;
        for (int i = 1 ; i < 26 ; i++) {
            for (int j = 0 ; j < i ; j++) {
                res += (size[i] - intersection[i][j]) * (size[j] - intersection[i][j]);
            }
        }
        return res << 1;
    }
}
